package org.hot100_1;

import org.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class leetcode43 {

    TreeNode pre =null;
    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }
        boolean leftIsValid = isValidBST(root.left);
        if (!leftIsValid){
            return false;
        }

        if (pre!=null && pre.val>=root.val){
            return false;
        }

        pre = root;

        boolean rightIsValid = isValidBST(root.right);

        return rightIsValid;
    }

    public boolean isValidBST2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        getList(root,list);
        for (int slow = 0,fast=1; fast < list.size();slow++,fast++) {
            if (list.get(fast)<=list.get(slow)){
                return false;
            }
        }

        return true;
    }

    private void getList(TreeNode root,List<Integer>list){
        if (root==null){
            return;
        }
        //中序遍历
        getList(root.left,list);
        list.add(root.val);
        getList(root.right,list);
    }

    public static void main(String[] args) {

    }



}
